#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
using namespace std;

 // Definition for singly-linked list.
  struct ListNode {
      int val;
      ListNode *next;
      ListNode() : val(0), next(nullptr) {}
      ListNode(int x) : val(x), next(nullptr) {}
      ListNode(int x, ListNode *next) : val(x), next(next) {}
  };
 
class Solution {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        int t = 0;
        ListNode* front = new ListNode(0);
        ListNode* head = front;
        ListNode* curr1 = l1;
        ListNode* curr2 = l2;
        while(curr1!=nullptr&&curr2!=nullptr){
            int value = curr1->val+curr2->val+t;
            if(value<10){
                head->next = new ListNode(value);
                head = head->next;
                t = 0;
            }
            else{
                head->next = new ListNode(value%10);
                head = head->next;
                t=1;
            }
            curr1 = curr1->next;
            curr2 = curr2->next;
        }
        if(t == 0){
            if(curr1!=nullptr){
                head->next = curr1;
            }
            if(curr2!=nullptr){
                head->next = curr2;
            }
        }
        else{
            ListNode* curr = (curr1!=nullptr)? curr1:curr2;
            while(curr!=nullptr){
                int value = curr->val+t;
                if(value<10){
                    head->next = new ListNode(value);
                    head = head->next;
                    t = 0;
                }
                else{
                    head->next = new ListNode(value%10);
                    head = head->next;
                    t=1;
                }
                curr = curr->next;

            }
            if(t==1){
                head->next = new ListNode(1);
                head->next->next = nullptr;
            }
        }
        return front->next;

    }
};

int main(){
    Solution S;
    ListNode* head = new ListNode(9);
    head->next = new ListNode(9);
    head->next->next = new ListNode(9);
    head->next->next->next = new ListNode(9);
    head->next->next->next->next = new ListNode(9);
    head->next->next->next->next->next = new ListNode(9);
    head->next->next->next->next->next->next = new ListNode(9);
    ListNode* head1 = new ListNode(9);
    head1->next = new ListNode(9);
    head1->next->next = new ListNode(9);
    head1->next->next->next = new ListNode(9);
    ListNode* T = S.addTwoNumbers(head,head1);
    return 0;
}